#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <set>

using namespace std;

// 辅助函数：打印数组
template<typename T>
void printArray(const vector<T>& arr) {
    for (const auto &elem : arr)
        cout << elem << " ";
    cout << endl;
}

/*
 1. 冒泡排序 (Bubble Sort)
    时间复杂度：
     - 最坏和平均：O(n^2)
     - 最好：O(n) （当数组已经有序时）
*/
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

/*
 2. 选择排序 (Selection Sort)
    时间复杂度：O(n^2)
*/
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

/*
 3. 插入排序 (Insertion Sort)
    时间复杂度：
      - 最坏和平均：O(n^2)
      - 最好：O(n)
*/
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

/*
 4. 归并排序 (Merge Sort)
    时间复杂度：O(n log n)
*/
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

void mergeSortHelper(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSortHelper(arr, left, mid);
        mergeSortHelper(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void mergeSort(vector<int>& arr) {
    mergeSortHelper(arr, 0, arr.size() - 1);
}

/*
 5. 快速排序 (Quick Sort)
    时间复杂度：
      - 平均：O(n log n)
      - 最坏：O(n^2) （极端情况下）
*/
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i + 1;
}

void quickSortHelper(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSortHelper(arr, low, pi - 1);
        quickSortHelper(arr, pi + 1, high);
    }
}

void quickSort(vector<int>& arr) {
    quickSortHelper(arr, 0, arr.size() - 1);
}

/*
 6. 堆排序 (Heap Sort)
    时间复杂度：O(n log n)
*/
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;  // 当前根
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    // 建立最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // 逐步提取最大元素
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

/*
 7. 希尔排序 (Shell Sort)
    时间复杂度：
      - 最坏：O(n^2)
      - 平均：取决于间隔序列，通常优于简单的 O(n^2) 算法
*/
void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

/*
 8. 计数排序 (Counting Sort)
    时间复杂度：O(n + k)  其中 k 为数组元素范围
    注意：适用于整数，且要求数据范围不大
*/
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int max_val = *max_element(arr.begin(), arr.end());
    int min_val = *min_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;
    vector<int> count(range, 0);
    for (int num : arr)
        count[num - min_val]++;
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];
    vector<int> output(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }
    arr = output;
}

/*
 9. 基数排序 (Radix Sort)
    时间复杂度：O(n * d)  d 表示数字的位数
    注意：一般用于整数排序
*/
int getMax(const vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

void radixSort(vector<int>& arr) {
    int n = arr.size();
    int max_val = getMax(arr);
    for (int exp = 1; max_val/exp > 0; exp *= 10) {
        vector<int> output(n);
        vector<int> count(10, 0);
        for (int i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        arr = output;
    }
}

/*
 10. 桶排序 (Bucket Sort)
     时间复杂度：平均 O(n) 当输入数据均匀分布时
     注意：这里使用浮点数数组，要求数据在 [0,1) 区间
*/
void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n <= 0)
        return;
    vector<vector<float>> buckets(n);
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i]; // 将数分布到 n 个桶中
        buckets[bucketIndex].push_back(arr[i]);
    }
    for (int i = 0; i < n; i++)
        sort(buckets[i].begin(), buckets[i].end());
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (float val : buckets[i])
            arr[index++] = val;
    }
}

/*
 11. 树排序 (Tree Sort)
     时间复杂度：
       - 平均：O(n log n)
       - 最坏：O(n^2)（当树不平衡时）
     实现方法：利用 C++ STL 的 std::set（底层是平衡二叉搜索树）来排序
*/
void treeSort(vector<int>& arr) {
    set<int> tree(arr.begin(), arr.end());
    int index = 0;
    for (int num : tree) {
        arr[index++] = num;
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    vector<int> arr_copy;

    cout << "Original array: ";
    printArray(arr);

    // 1. 冒泡排序
    arr_copy = arr;
    bubbleSort(arr_copy);
    cout << "Bubble Sort: ";
    printArray(arr_copy);

    // 2. 选择排序
    arr_copy = arr;
    selectionSort(arr_copy);
    cout << "Selection Sort: ";
    printArray(arr_copy);

    // 3. 插入排序
    arr_copy = arr;
    insertionSort(arr_copy);
    cout << "Insertion Sort: ";
    printArray(arr_copy);

    // 4. 归并排序
    arr_copy = arr;
    mergeSort(arr_copy);
    cout << "Merge Sort: ";
    printArray(arr_copy);

    // 5. 快速排序
    arr_copy = arr;
    quickSort(arr_copy);
    cout << "Quick Sort: ";
    printArray(arr_copy);

    // 6. 堆排序
    arr_copy = arr;
    heapSort(arr_copy);
    cout << "Heap Sort: ";
    printArray(arr_copy);

    // 7. 希尔排序
    arr_copy = arr;
    shellSort(arr_copy);
    cout << "Shell Sort: ";
    printArray(arr_copy);

    // 8. 计数排序
    arr_copy = arr;
    countingSort(arr_copy);
    cout << "Counting Sort: ";
    printArray(arr_copy);

    // 9. 基数排序
    arr_copy = arr;
    radixSort(arr_copy);
    cout << "Radix Sort: ";
    printArray(arr_copy);

    // 10. 桶排序测试（浮点数数组，要求在 [0,1) 区间）
    vector<float> arr_float = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f};
    cout << "Original float array: ";
    printArray(arr_float);
    bucketSort(arr_float);
    cout << "Bucket Sort: ";
    printArray(arr_float);

    // 11. 树排序
    arr_copy = arr;
    treeSort(arr_copy);
    cout << "Tree Sort: ";
    printArray(arr_copy);

    return 0;
}
